#define _CRT_SECURE_NO_WARNINGS 1
class PalindromeList {
public:
    struct ListNode* FindMidNode(struct ListNode* Head)
    {
        struct ListNode* slow, * fast;
        slow = fast = Head;
        while (fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    struct ListNode* ReverseList(struct ListNode* Head)
    {
        struct ListNode* cur = Head;
        struct ListNode* RHead = NULL;
        while (cur != NULL)
        {
            struct ListNode* Next = cur->next;
            cur->next = RHead;
            RHead = cur;
            cur = Next;
        }
        return RHead;
    }
    bool chkPalindrome(ListNode* A)
    {
        struct ListNode* mid = FindMidNode(A);
        struct ListNode* Head = ReverseList(mid);
        while (Head->next != NULL)
        {
            if (A->val != Head->val)
                return false;

            A = A->next;
            Head = Head->next;
        }
        return true;
    }
};
